﻿#include <iostream>
#include "SlidingWindow.h"

SlidingWindow::SlidingWindow(const int* numbers, size_t size)
{
    this->numbers = (int*)malloc(size * sizeof(int));
    memcpy(this->numbers, numbers, size * sizeof(int));
    numberSize = size;
    left = -1;
    right = -1;
}

SlidingWindow::~SlidingWindow()
{
    if (numbers)
    {
        free(numbers);
        numbers = nullptr;
    }
}

void SlidingWindow::stepRight()
{
    if (right + 1 >= numberSize) return;

    ++right;
    while (!numDeque.empty() && numbers[right] >= numbers[numDeque.back()])
    {
        numDeque.pop_back();
    }

    numDeque.push_back(right);
}

void SlidingWindow::stepLeft()
{
    if (left >= right) return;

    ++left;
    while (!numDeque.empty() && left == numDeque.front())
    {
        numDeque.pop_front();
    }
}

int SlidingWindow::maxValue()
{
    if (numDeque.empty()) return -1;

    return numbers[numDeque.front()];
}

/**
 * 滑动窗口
 *
 * L R
 * | |  3  2  4  6  0  1  7
 *
 * L可以右移，R可以右移，L不能超过R的位置，L和R之间的数字即为窗口中的数字.
 * 举例，任意窗口的最大值
 *
 *       L R
 *       | |   3  2  4  6  3  5  4  3  5
 * index:      0  1  2  3  4  5  6  7  8
 *
 * 双端队列：
 *
 *          |                          |
 *          从左到右，数字要从大到小。
 *
 * (1) R右移一次：
 *       L       R
 *       |     3 |2  4  6  3  5  4  3  5
 * index:      0  1  2  3  4  5  6  7  8
 *
 * 双端队列:
 *                  3
 *                  ↑
 *              |   0        |
 * 第0元素从队列右侧加入到队列。任何时候窗口的最大值即为队列头部，也就是左侧的第一个元素.
 *
 * (2) R右移一次:
 *       L          R
 *       |     3  2 |4  6  3  5  4  3  5
 * index:      0  1  2  3  4  5  6  7  8
 *
 * 双端队列:
 *                  3  2
 *                  ↑ ↑
 *              |   0  1        |
 * 由于第1元素小于第0元素，故可以直接从右侧加入到队列.
 *
 * (3) R右移一次:
 *       L             R
 *       |     3  2  4 |6  3  5  4  3  5
 * index:      0  1  2  3  4  5  6  7  8
 *
 * 双端队列:
 *                  3  2                4
 *                  ↑ ↑               ↑
 *              |   0  1        |   ←←2
 * 此时，第2元素要加入队列，但是发现第0和第1都比它小，不符合从左至右由大到小的规则，故需要将队列中的前2个元素，从右侧弹出队列，再把第2元素放入。
 *
 * 双端队列:
 *                  4                  3   2
 *                  ↑                 ↑  ↑
 *              |   2           |  →→ 0  1
 *
 * (4) R右移一次:
 *       L                R
 *       |     3  2  4  6 |3  5  4  3  5
 * index:      0  1  2  3  4  5  6  7  8
 * 和上一步一样，第3元素比第2元素大，故第2元素需要从队列右侧弹出，再把第3元素压入队列
 *
 * 双端队列:
 *                   6                4
 *                  ↑                ↑
 *              |   3           |  →→2
 *
 * (5) R右移一次:
 *       L                   R
 *       |     3  2  4  6  3 |5  4  3  5
 * index:      0  1  2  3  4  5  6  7  8
 *
 * 双端队列:
 *                   6  3
 *                  ↑  ↑
 *              |   3   4       |
 *
 * (6) R右移一次:
 *       L                      R
 *       |     3  2  4  6  3  5 |4  3  5
 * index:      0  1  2  3  4  5  6  7  8
 *
 * 双端队列:
 *                   6  5                3
 *                  ↑  ↑               ↑
 *              |   3   5       |   →→ 4
 *
 * (7) R右移一次:
 *       L                         R
 *       |     3  2  4  6  3  5  4 |3  5
 * index:      0  1  2  3  4  5  6  7  8
 *
 * 双端队列:
 *                   6  5    4
 *                  ↑  ↑   ↑
 *              |   3   5   6   |
 * ......
 *
 *       L R
 *       | |   6  4  2  5  3
 * index:      0  1  2  3  4
 *
 * 双端队列：
 *
 *          |                          |
 *          从左到右，数字要从大到小。
 * (1) R右移3次
 *       L             R
 *       |     6  4  2 |5  3
 * index:      0  1  2  3  4
 *
 * 双端队列:
 *                   6  4    2
 *                  ↑  ↑   ↑
 *              |   0   1   2   |
 *
 * (2) L右移1次
 *               L     R
 *             6 |4  2 |5  3
 * index:      0  1  2  3  4
 *
 * L右移看过期的元素是否是队列头部元素，也就是最左侧的元素，如果是，则从队列左侧弹出头部元素。
 *
 * 双端队列:
 *         6         4    2
 *        ↑         ↑   ↑
 *        0 ←← |   1   2   |
 *
 * (3) R右移2次
 *               L          R
 *             6 |4  2  5  3|
 * index:      0  1  2  3  4
 *
 * 双端队列:
 *                   5  3
 *                  ↑  ↑
 *              |   3   4     |
 *
 * (4) L右移1次
 *                  L       R
 *             6  4 |2  5  3|
 * index:      0  1  2  3  4
 *
 * 队列中没有第1元素，则不改动队列
 *
 * 双端队列:
 *                   5  3
 *                  ↑  ↑
 *              |   3   4     |
 *
 * (5) L右移1次
 *                     L    R
 *             6  4  2 |5  3|
 * index:      0  1  2  3  4
 *
 * 队列中没有第2元素，则不改动队列
 *
 * 双端队列:
 *                   5  3
 *                  ↑  ↑
 *              |   3   4     |
 *
 * (6) L右移1次
 *                        L R
 *             6  4  2  5 |3|
 * index:      0  1  2  3  4
 *
 * 队列中没有第2元素，则不改动队列
 *
 * 双端队列:
 *           5            3
 *          ↑            ↑
 *          3 ←←   |    4      |
 *
 * 本质上，L右移的意义是，在R不动的前提下，谁是目前窗口中的最大值.
 */
int main_SlidingWindow()
{
    int arr[] = { 1,5,4,6,2,3,9,7 };
    SlidingWindow* window = new SlidingWindow(arr, sizeof(arr) / sizeof(int));

    for (int i = 0; i < 3; i++)
    {
        window->stepRight();
    }

    window->stepLeft();
    printf("max=%d\n", window->maxValue());

    return 0;
}